import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/7 11:20
 * @description 单调栈正序遍历
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i = 0; i  < n; i++) {
            while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
                prices[stack.peek()] -= prices[i];
                stack.pop();
            }
            stack.push(i);
        }
        return prices;
    }
}
